package prac3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * To learn how stacks can be used to evaluate mathematical equations in Reverse Polish Notation.
 * 
 * @author          Brendon Taylor
 * @modified        Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
 *                  Brendon Taylor (Feb 2010) - JavaDoc
 *                  Maria (March 2011) - Details
 *                  Monghong Li (Aug 2011)
 * @since           March 6, 2009
 * @input           menuQ1: menu option from keyboard
 * @input           main: question number from keyboard
 * @output          menuQ1: the menu
 * @errorHandling   IOException: Error reading keyboard
 * @errorHandling   NumberFormatException: Non-integer input
 * @knownBugs       none
 */

public class ReversePolishNotation {
    /** represents the maximum number of elements in our stack */
    public static final int STACK_SIZE = 10;
    
    /**
     * Skeleton code for Question 1.
     * 
     * @param        keyboard used to read from standard input (keyboard)
     * @complexity   best case one could say O(1) if the user immediately exits
     *      but this is similar to saying Empty. So, assuming a high 
     *      number of iterations N, the complexity is O(N)*BigOCase. 
     *      where BigOCase is the complexity of the option selected.
     *      Thus, best case is when we always asks for an option that is O(1), 
     *      like getSize. Worst case is when one often asks for the most
     *      expensive option, like printing all the elements in the stack.
     *
     *        *NOTE: you should update this as the code changes
     */
    public static void menuQ1(BufferedReader keyboard) {
        int option = -1;
        IntStack myStack = new IntStack(STACK_SIZE);

        // While the user has not selected exit 
        while (option != 5) {
            System.out.println("1. Push");
            System.out.println("2. Pop");
            System.out.println("3. Print");
            System.out.println("4. Size");
            System.out.println("5. Exit");

            try {
                option = Integer.parseInt(keyboard.readLine());
                // While we have invalid input
                while (option < 1 || option > 5) {
                    System.out.println("Invalid integer entered, try again");
                    option = Integer.parseInt(keyboard.readLine());
                }

                // Process Option

                /* INSERT YOUR CODE HERE */
                switch (option) {
                case 1: 
                {
                	System.out.println("Input an integer: ");
                	int num;
                	try {
                		num = Integer.parseInt(keyboard.readLine());
                	} catch(NumberFormatException e){
                		System.out.println("Invalid string");
                		break;
                	}
                	try {
                		myStack.push(num);
                	} catch (Exception e) {
                		System.out.println("Unable to push into the stack.");
                	}
                	break;
                }
                	
                case 2:
                {
                  	try {
						System.out.println(myStack.pop());
					} catch (Exception e) {
						System.out.println("Unable to pop from the stack.");
					}                	
                	break;
                }
                case 3:
                	System.out.println(myStack.toString());
                	break;
                case 4:
                	System.out.println(myStack.getSize());
                	break;
                case 5:
                	System.exit(0);
                }
            }
            catch(IOException e) {
                System.out.println("menuQ1: " + e);
            }
            catch(NumberFormatException e) {
                System.out.println("menuQ1: " + e + ", integer expected");
            }
        }
    }
    
    /**
     * prompts the user for a character string, splits it into its substrings (using spaces as the delimiters)
     * and prints out each substring together with a message indicating whether the substring is an integer, 
     * an operator (accepted operators will be addition, subtraction, multiplication, division, and equality,
     *  i.e., +, -, *, /), or an invalid string.
     * 
     * @param       keyboard used to read from standard input (keyboard)
     * @throws      IOException 
     * @pre         nothing
     * @post        substring printed
     * @complexity  best case and worst case O(N)
     */
    public static void splitQ2(BufferedReader keyboard) throws IOException{
    	System.out.println("Input an expression >> ");
    	String expression = keyboard.readLine();
    	String[] splitExp=expression.split(" ");
    	for(String i:splitExp){
    		if(i.compareTo("+")==0){
    			System.out.println("+ Operator");
			} 
			else if (i.compareTo("-") == 0) {
				System.out.println("- Operator");
			}
			else if (i.compareTo("*") == 0) {
				System.out.println("* Operator");
			}
			else if (i.compareTo("/") == 0) {
				System.out.println("/ Operator");
			}else if (i.matches("-?[0-9]*")) {
				System.out.println(i+" "+"Integer");
			}
			else {
				System.out.println(i+" "+"Invalid string");
			}
    	}
    }
    
    /**
     * Quits or evaluates the expression and prints out the result
     * 
     * @param       keyboard used to read from standard input (keyboard)
     * @pre         nothing
     * @post        quit or the result of the expression printed out
     * @complexity  best and worst case: O(sizeOfValidInput)
     */
    public static void menuQ3(BufferedReader keyboard){
        int option = -1;
        IntStack myStack = new IntStack(STACK_SIZE);

        // While the user has not selected exit 
        while (option != 2) {
            System.out.println("1. Enter a Reverse Polish Notation");
            System.out.println("2. Exit");

            try {
                option = Integer.parseInt(keyboard.readLine());
                // While we have invalid input
                while (option < 1 || option > 2) {
                    System.out.println("Invalid integer entered, try again");
                    option = Integer.parseInt(keyboard.readLine());
                }

                switch (option) {
                case 1: 
                {
                	int num;
                	System.out.println("Input an Reverse Polish Notation >> ");
                	String expression= keyboard.readLine();
                	String[] splitExp=expression.split(" ");
                	for(String i:splitExp){
                		if(i.compareTo("+")==0){
                			try {
								num=myStack.pop();
								num=myStack.pop()+num;
								myStack.push(num);
							} catch (Exception e) {
								System.out.println("Unable to pop from the stack.");
							}
                			
            			} 
            			else if (i.compareTo("-") == 0) {
            				try {
								num=myStack.pop();
								num=myStack.pop()-num;
								myStack.push(num);
							} catch (Exception e) {
								System.out.println("Unable to pop from the stack.");
							}
            			}
            			else if (i.compareTo("*") == 0) {
            				try {
								num=myStack.pop();
								num=myStack.pop()*num;
								myStack.push(num);
							} catch (Exception e) {
								System.out.println("Unable to pop from the stack.");
							}
            			}
            			else if (i.compareTo("/") == 0) {
            				try {
            					if(myStack.top()==0){
            						System.out.println("cannot be 0");
            					}
								num=myStack.pop();
								num=myStack.pop()/num;
								myStack.push(num);
							} catch (Exception e) {
								System.out.println("Unable to pop from the stack.");
							}
            			}else if (i.matches("-?[0-9]*")) {
                        	try {
                        		num = Integer.parseInt(i);
                        		myStack.push(num);
                        	} catch(Exception e){
                        		System.out.println("Unable to push into the stack.");
                        	}
            			}
            			else {
            				System.out.println(i+" "+"Invalid string");
            			}
                	}
                	try {
						System.out.println("The result is :"+ myStack.top());
					} catch (Exception e) {
						e.printStackTrace();
					}
                	
                	break;
                }
                case 2:
                	System.exit(0);
                }
            }
            catch(IOException e) {
                System.out.println("menuQ3: " + e);
            }
            catch(NumberFormatException e) {
                System.out.println("menuQ3: " + e + ", integer expected");
            }
        }
    }
    
    /**
     * Reads integer infix expressions and prints out Reverse Polish expressions
     * 
     * @param       keyboard used to read from standard input (keyboard)
     * @throws      Exception 
     * @pre         nothing
     * @post        Reverse Polish expression printed
     * @complexity  best and worst case: O(sizeOfInvalidInput)
     */ 
    public static void infix2rpn(BufferedReader keyboard) throws Exception{
		try {
			IntStack myStack = new IntStack(STACK_SIZE);
			System.out.println("Input an Normal infix notation >> ");
			String expression = keyboard.readLine(); 
			for (int i = 0; i < expression.length(); i++) {
				try {
					if (Character.isDigit(expression.charAt(i))) {
						System.out.print(expression.charAt(i));
					}
					else if (expression.charAt(i) == '+' || expression.charAt(i) == '-') {
						if (myStack.isEmpty()) {
							myStack.push((int)expression.charAt(i));
						} else {
 							while (!myStack.isEmpty()) {
 								System.out.print((char)myStack.pop());
 							}
 							myStack.push((int)expression.charAt(i));
						}
					}
					else if (expression.charAt(i) == '*' || expression.charAt(i) == '/') {
						while (!myStack.isEmpty() && ((char)myStack.top() == '*' || (char)myStack.top() == '/') ){
							System.out.print((char)myStack.pop());
						}
						myStack.push((int)expression.charAt(i));
					}
					else {
						System.out.println("Invalid input, retry");
					}
						
				} catch (Exception e) {
					System.out.println("Exception : Invalid string, retry\n");
				}	
			}
			while (!myStack.isEmpty()) {
				System.out.print((char)myStack.pop());
			}
		} catch (IOException e) {
				System.out.println("Invalid expression ");
		}
    }
    
    public static void infixCalculator(BufferedReader keyboard) throws IOException{
    	   StringBuffer numBuffer = new StringBuffer();
           Stack<Character> opStack = new Stack<Character>();
           System.out.println("Input an infix notation >> ");
           String expression = keyboard.readLine();
           expression=expression+"#";
           char ch,preChar;
           opStack.push('#');
           try{
               for(int i = 0; i < expression.length();){
                  ch = expression.charAt(i);
                   switch(ch){
                        case '+':
                        case '-':
                       case '*':
                        case '/':
                            preChar = opStack.peek();
                            while(priority(preChar) >= priority(ch)){
                                System.out.print(opStack.pop());
                                preChar = opStack.peek();
                            }
                            opStack.push(ch);
                            i++;
                            break;
                       case '(':
                            opStack.push(ch);
                            i++;
                            break;
                       case ')':
                            char c = opStack.pop();
                            while(c != '('){
                                System.out.print(c);
                                c = opStack.pop();
                            }
                            i++;
                            break;
                     case '#':
                         char c1;
                         while(!opStack.isEmpty()){
                             c1 = opStack.pop();
                             if(c1 != '#')
                               System.out.print(c1);
                         }
                         i++;
                         break;
                     case ' ':
                     case '\t':
                         i++;
                         break;
                     default:
                         if(Character.isDigit(ch)){
                             while(Character.isDigit(ch)){
                                 numBuffer.append(ch);
                                 ch = expression.charAt(++i);
                             }
                             System.out.print(numBuffer.toString());
                             numBuffer = new StringBuffer();
                         }else{
                             throw new IllegalExpressionException("illegal operator");
                         }
                   }
               }
           }catch(RuntimeException e){
               throw new IllegalExpressionException(e.getMessage());
          }
    }
    public static int priority(char op){
        switch(op){
	        case'+':
	        	return 1;
	        case'-':
	            return 1;
	        case'*':
	        	return 2;
	        case'/':
	            return 2;
	        case'(': 
	        	return 0;
	        case'#':
	            return 0;
        }
        throw new IllegalExpressionException("Illegal operator");
  }

    /**
     * @param       args command-line arguments
     * @throws      Exception 
     * @complexity  best case:  O(1) - user enters an invalid question number
     *      but again, this is similar to saying Empty. So O(MenuQ1) if we
     *      assume all other operations (like readLine) are O(1)
     * @complexity  worst case: O(MenuQ1) - see {@link #menuQ1(BufferedReader)} 
     *              - i.e., the complexity of the menuQ1 method
     */
    public static void main(String[] args) throws Exception {
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader keyboard = new BufferedReader(input);

        try {
            System.out.print("Please enter question number: ");
            String question = keyboard.readLine();
        
            switch (Integer.valueOf(question)) {
                    case 1:   menuQ1(keyboard);  break;
                    case 2:   splitQ2(keyboard); break;
                    case 3:   menuQ3(keyboard);  break;
                    case 4:   infix2rpn(keyboard); break;
                    case 5:   infixCalculator(keyboard); break;
                    default:  System.out.println("Invalid question");
            }
        }
        catch(IOException e) {
            System.out.println("main: " + e);       
        }
        catch(NumberFormatException e) {
            System.out.println("main: " + e + ", integer expected");
        }
    }
}
